1. Field of the Invention
The present invention relates to a coding-decoding device and a coding-decoding method, in particular to a technique for converting a first sentence expressed in binary numbers into a second sentence expressed in binary numbers.
2. Description of Prior Art
The RSA coding system is known as one of coding systems. In the course of processing with the RSA coding system, a plain sentence M is ciphered into a coded sentence C according to the following equation using a public key (n, e) where n is a product of any two prime numbers p and q, and e is any number that satisfies a certain limitation to the prime numbers p and q:C=Me(mod n)
The coded sentence C may also be decoded into the plain sentence M according to the following equation using a secret key (n, d) where n is the same as the above and d is a number derived uniquely from the above e, and the prime numbers p and q:M=Cd(mod n)
Here, if a third person succeeds in solving the n of the public key (n, e) to derive the prime numbers p and q, the person can easily find the d based on the prime numbers and e, and obtain the secret key (n, d).
However, if the value of the above n is increased, factoring for obtaining the p and q takes enormous time, making it practically impossible to decode. In this way, the RSA coding system secures its security by increasing the value of the n.
However, the conventional RSA coding system has so far been faced with the following problems. That is to say, the coding requires e times of multiplication with the plain sentence M. And its decoding requires d times of multiplication with the coded sentence C. Therefore, the problem is that the greater the n for higher security, the longer the time taken for coding and decoding.
To solve the above problem, it is conceivable to use a coding circuit constituted with hardware only. FIG. 10 shows a circuit 1, corresponding to 1 bit of the coded sentence, of a coding circuit for converting a b-bit plain sentence into a b-bit coded sentence.
The circuit 1 is constituted with 2b−1 pieces of b-input AND gates 3 and 1 piece of 2b−1 input OR gate 5. Therefore, the entire coding circuit requires logic gates that are b times in number of the above. While using this type of coding circuit can reduce the time for coding, enormous number of logic gates is required. The problem is the same for decoding.